#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
#define LLD long long int

using namespace std;

const int INF = 0x7fffffff;

class GRAPH {
   public:
    // const int INF = 0x7fffffff;
    struct EDGE {
        int src, dest;
        LLD weight;
        EDGE() : src(0), dest(0), weight(INF) {}
        EDGE(int s, int d, LLD w) : src(s), dest(d), weight(w) {}
        EDGE(int d, LLD w) : dest(d), weight(w) {}
    };

    struct NODE {
        int ind;
        LLD val;
        NODE() : ind(0), val(0) {}
        NODE(int i, LLD v) : ind(i), val(v) {}
        bool operator<(const NODE &n1) const {
            return n1.val < val;
        }
    };

    int nodeNum;
    vector<LLD> dis;  // distance from source-point to target-point
    vector<int> fnt;  // optimal solution: the last-point of target-point in the optimal path
    vector<bool> vis;
    vector<vector<EDGE>> G;

    GRAPH(int n) : nodeNum(n), dis(n + 1, INF), fnt(n + 1, 0), vis(n + 1, false), G(n + 1, vector<EDGE>(0)) {}

    void AddEdge(int src, int dest, LLD weight) {
        G[src].push_back(EDGE(src, dest, weight));
    }

    void DIJKSTRA(int src) {
        priority_queue<NODE> pq;
        dis[src] = 0;
        pq.push(NODE(src, 0));
        while (!pq.empty()) {  //!!
            NODE u = pq.top();
            pq.pop();
            int n = u.ind;
            LLD d = u.val;
            if (vis[n])
                continue;
            vis[n] = true;

            for (int j = 0; j < (int)G[n].size(); j++) {
                int v = G[n][j].dest;
                if (dis[v] <= d + G[n][j].weight) continue;
                dis[v] = d + G[n][j].weight;
                fnt[v] = n;
                if (!vis[v]) pq.push(NODE(v, dis[v]));
            }
        }
    }

    void PRINTDIS() {
        for (int i = 1; i <= nodeNum; i++)
            cout << dis[i] << " ";
        cout << endl;
    }
};

int main() {
    // freopen("D:\\.MLGit\\pytorch_workplace\\WorkPlace\\DATA-STRUCTURE-ALGORITHM\\P4779_1.in", "r", stdin);
    // freopen("D:\\.MLGit\\pytorch_workplace\\WorkPlace\\DATA-STRUCTURE-ALGORITHM\\P4779myout.out", "w", stdout);
    int n, m, s;
    cin >> n >> m >> s;
    GRAPH g(n);
    for (int i = 0; i < m; i++) {
        int f, t, w;
        cin >> f >> t >> w;
        g.AddEdge(f, t, w);
    }
    g.DIJKSTRA(s);
    g.PRINTDIS();
    //     fclose(stdin);
    //     fclose(stdout);
}